\chapter{Introdução}\label{cap1}

\section{Motivação}

O poder de processamento dos computadores vem crescendo muito nos últimos anos. Já é comum, inclusive, computadores pessoais terem mais de um processador. Desenvolver programas ou algoritmos que não utilizam completamente os recursos disponíveis nas máquinas resulta em um desperdício de capacidade de processamento.

Ainda é preciso, entretanto, desenvolver técnicas que tentem alcançar uma boa escalabilidade, ou seja, ter um aumento no seu desempenho quando mais recursos computacionais forem disponíveis, mantendo ou melhorando os resultados obtidos pelo algoritmo sequencial. 

    \begin{figure}[h]
    \centering
    \subfloat[Malha de computação gráfica. Fonte: www.yofrankie.org.]
    {\label{fig:ex_malha}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/ex_malha.png}}\end{minipage}
    }
    \qquad
    \subfloat[Malha de sistemas de informação geográfica. Fonte: classics.uc.edu.]
    {\label{fig:SIG_mesh}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/SIG_mesh.png}}\end{minipage}
    }
    
    \subfloat[Malha de projetos assistidos por computadores. Fonte: www.research.ibm.com.]
    {\label{fig:CAD_mesh}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/CAD_mesh.png}}\end{minipage}
    }    
    \qquad
    \subfloat[Malha utilizada na engenharia para MEF.]
    {\label{fig:MEF_mesh}
     \begin{minipage}[c]{0.45\textwidth}{\includegraphics[width=\textwidth]{fig/MEF_mesh.png}}\end{minipage}
    }
    \caption{Exemplos de aplicações para malhas.}
    \label{fig:aplicações para malhas}
    \end{figure}

Malhas estão presentes no nosso dia a dia e são amplamente utilizadas para representar geometrias e outras informações. Alguns exemplos de aplicações seriam: em computação gráfica (CG) (Figura \ref{fig:ex_malha}), sistemas de informações geográficas (SIG) (Figura \ref{fig:SIG_mesh}), projetos assistidos por computadores (CAD) (Figura \ref{fig:CAD_mesh}) e na engenharia, ajudando na análise e simulação de fenômenos físicos que utilizam métodos de elementos finitos (MEF) (Figura \ref{fig:MEF_mesh}). 

Grandes malhas são necessárias em aplicações reais para obter bons resultados. Além do tamanho, a qualidade dos elementos da malha é fundamental em algumas aplicações como as da Engenharia. Então, para um bom programa de geração de malha executar, é necessário que ele também rode em paralelo e garanta que a malha gerada seja tão boa quanto a malha gerada sequencialmente. No MEF, por exemplo, se uma malha tiver uma grande quantidade de elementos ruins (polígonos, em malhas bidimensionais), é possível que este não convirja. Por necessitar de malhas bastante refinadas, é comum que as análises de elementos finitos usem malhas grandes, com milhões de elementos.

A geração de malha em paralelo geralmente envolve duas fases distintas, a decomposição ou partição do domínio em partes menores, que são enviadas para os processadores que estão disponíveis e a geração de malha em cada uma dessas partes, chamadas de subdomínios. Em geral se usa a mesma técnica de geração para cada um dos subdomínios usados, como triangulação de Delaunay ou Avanço de Fronteira, por exemplo, o que pode ser uma restrição para a geração.  Além disso, deve-se procurar obter a melhor escalabilidade possível, a fim de utilizar corretamente todos os recursos disponíveis dos computadores.


\section{Objetivos e Contribuições}

O principal objetivo deste trabalho é descrever uma técnica \textit{a priori} de subdivisão de domínios bidimensionais para geração paralela da malha. A técnica proposta é dita \textit{a priori} porque a malha de interface entre os subdomínios é gerada antes das suas malhas internas. Essa técnica gera novos domínios e permite abstrair a técnica de geração de malha aplicada aos subdomínios, podendo-se combinar, por exemplo, as técnicas de Delaunay e Avanço de Fronteira, dentre outras. Além disso, a técnica proposta permite também abstrair o tipo de arquitetura de memória a ser usada (compartilhada ou distribuída).

A técnica foi projetada para atender aos seguintes requisitos:
\begin{enumerate}
  \item Respeitar a fronteira de entrada, discretizada em segmentos, sem efetuar refinamentos;

  \item Produzir bons elementos, evitando-se elementos com proporções ruins;

  \item Proporcionar boas transições entre as regiões muito refinadas, com muitos triângulos pequenos, e regiões grosseiras, com poucos triângulos grandes, da malha;

  \item Manter a compatibilidade das fronteiras (segmentos de interface) dos subdomínios criados com as de seus vizinhos;
 
  \item Abstrair a técnica de geração de malha, podendo-se combinar mais de uma técnica;
  
  \item Abstrair o tipo de arquitetura de memória a ser usada (compartilhada ou distribuída); e
  
  \item Tentar gerar malhas da forma mais eficiente possível.
\end{enumerate}



\section{Organização do Trabalho}

O restante deste trabalho está organizado em quatro capítulos. No Capítulo \ref{cap2}, apresentam-se alguns conceitos de Geometria Computacional e de Computação de Alto Desempenho necessários à compreensão dos capítulos subsequentes. No Capítulo \ref{cap3}, é apresentada uma visão geral das técnicas de subdivisão de domínios para geração paralela de malhas. No Capítulo \ref{cap4}, é apresentada a técnica de subdivisão de domínios bidimensionais desenvolvida, detalhando a técnica e a criação das estruturas de dados envolvidas no processo de estimativa da carga e particionamento do domínio. No Capítulo \ref{cap5}, são apresentados os resultados dos testes preparados para demonstrar a eficácia da técnica proposta, e os resultados obtidos são analisados. Por fim, no Capítulo \ref{cap6}, são apresentadas as conclusões sobre o trabalho e são propostas algumas ideias para trabalhos futuros.
